package com.niuke;

import com.pojo.ListNode;

/**
 * Description:
 * Copyright:   Copyright (c)2019
 * Company:     zefu
 *
 * @author: 张李鑫
 * @version: 1.0
 * Create at:   2021-12-13 01:00:37
 * <p>
 * Modification History:
 * Date         Author      Version     Description
 * ------------------------------------------------------------------
 * 2021-12-13     张李鑫                     1.0         1.0 Version
 */
public class JZ23 {

    /**
     * 给一个长度为n链表，若其中包含环，请找出该链表的环的入口结点，否则，返回null。
     * <p>
     * 数据范围： n\le10000n≤10000，1<=结点值<=100001<=结点值<=10000
     * 要求：空间复杂度 O(1)O(1)，时间复杂度 O(n)O(n)
     *
     * @param pHead
     * @return
     */
    public static ListNode EntryNodeOfLoop(ListNode pHead) {
        if (pHead == null || pHead.next == null || pHead.next.next == null) {
            return null;
        }
        ListNode cur = pHead;
        ListNode next = pHead;


        while (next != null) {
            cur = cur.next;
            next = next.next == null ? null : next.next.next;
            if (cur == next) {
                cur=pHead;
                if (next==pHead){
                    return pHead;
                }else {
                    break;
                }
            }
        }

        while (next!=null){
            cur=cur.next;
            next=next.next;
            if (cur==next){
                return cur;
            }
        }

        return null;
    }

    public static void main(String[] args) {
        ListNode listNode=new ListNode(1);
        ListNode listNode1=new ListNode(2);
        ListNode listNode2=new ListNode(3);
        ListNode listNode3=new ListNode(4);
        ListNode listNode4=new ListNode(5);

        listNode.next=listNode1;
        listNode1.next=listNode2;
        listNode2.next=listNode3;
        listNode3.next=listNode4;
        listNode4.next=listNode;

        System.out.println(EntryNodeOfLoop(listNode));
    }
}